406. 根据身高重建队列

Similar Question

135. 分发糖果

Solution Tips

方案一: 哈希表 + 模拟

var reconstructQueue = function(people) {
    // 所有 k 为 0 的都是靠前的, 可以先进行一次排列, 但是不一定, 也许有人很高
    // 身高越矮, 同时 k 值越小的也会越靠前
    // 最矮的人前面每个人都会比他高, 所以 k 就是他的 index, 这个位置固定的
    // 第二矮的人, 两面有2个人比他高, 所以只能放在 2 的位置, 为啥呢? 错的, 可以放在 1 的后面, 前面再塞2个就好了
    // 第一矮的人, 给第二矮的人划分了前后, 如果要在 1 的后面, 就要求 2 的前面还会有 k1 个比他高的人
    // 因为只有1比他矮, 所以如果放后面, 且 k1 大于 k2 就不行了, 那么只能放前面, 在前面的话就是单一的选择, 只能放在第二个位置
    // 但是这个逻辑太难转化成代码了
    // 3 也不能放在 1 的后面, 因为2个比他矮的都在前面了, 还有3个空位, 不能满足 k
    // 后面所有的人都比自己高, 只能排在空余 index 的第 k 个位置
    // 值相同的要一起排列就可以了, 又是一题优先队列
    // 我还是只能使用哈希表, 并不会优先队列
    const orderMap = {};
    for (let i = 0; i < people.length; i++) {
        const item = people[i];
        const [h, k] = item;
        if (!orderMap[h]) {
            orderMap[h] = [item];
        }
        else {
            orderMap[h].push(item);
        }
    }

    const res = Array.from({ length: people.length });
    for (const list of Object.values(orderMap)) {
        const listOrder = [];
        for (let i = 0; i < list.length; i++) {
            const item = list[i]
            const [h, k] = item;
            // 在剩余的位置填入 item
            // empty 的计算, 同身高的是共享的, k 还得排排序, 小的先来
            let empty = -1;
            for (let i = 0; i < res.length; i++) {
                if (!res[i]) {
                    empty++;
                    if (empty === k) {
                        // 先不急着 设置, 都跑完了再设置就好了
                        listOrder.push(i);
                        break;
                    }
                }
            }
        }
        // 设置
        for (let i = 0; i < list.length; i++) {
            res[[listOrder[i]]] = list[i];
        }
    }

    return res;
};
console.log(reconstructQueue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]))

方案二: 优先队列 + 模拟

方案三: 贪心